Final Assignment CIT130: MAZE

Final Assignment CIT 130 Fall 2003 - Maze Generator

Your assignment is to use the following 2 files:
MazeOut.java
MazeOut.java
to construct a maze generator/solver.

MazeOut gives you the code to display a maze and Cell gives you the definition of a single cell.

The algorithm for generating a maze is based on set theory:

create a matrix of cells - in this case 30x30 or 900 cells

put each of the cells into a set - use a vector to hold the sets

Since Set is not instantable, use HashSet

randomly choose a cell and randomly choose a contiguous (n/s/e/w) neighbor

if the 2 cells are are in the same set reject

if the 2 cells are in seperate sets, join them and join their sets

repeat until the upper left and lower right are in the same set

The solution is the standard maze recursive solution recursiveSolve(x,y)

if (x,y outside maze) return false
if (x,y is goal) return true
if (x,y not open) return false
mark x,y as part of solution path
if (recursiveSolveMaze(North of x,y) == true) return true
if (recursiveSolveMaze(East of x,y) == true) return true
if (recursiveSolveMaze(South of x,y) == true) return true
if (recursiveSolveMaze(West of x,y) == true) return true
unmark x,y as part of solution path
return false

Here is an example in a self extracting jar file.

Maze

You can make yours either an applet or application.